package sol.leetcode;

import utils.ArrayUtils;

/**
 * CPerfect Squares
 */
public class Issue279 {
    public int numSquares(int n) {

        int sqrt = (int) Math.sqrt(n);
        int[][] s = new int[sqrt + 1][n + 1];
        for (int i = 0; i <= sqrt; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (i == 0) s[i][j] = Integer.MAX_VALUE;
                else if (j == 0) s[i][j] = 0;
                else if (i * i > j) s[i][j] = s[i - 1][j];
                else {
                    int a = s[i - 1][j];//不加入i*i
                    int b = s[i][j - i * i] + 1;//加入1*1
                    s[i][j] = Math.min(a, b);
                }
            }
        }

        ArrayUtils.print(s);
        return s[sqrt][n];
    }

    public static void main(String[] args) {
        int n = 13;
        Issue279 sol = new Issue279();
        System.out.println(sol.numSquares(n));
    }
}
